package graph;

import unionfindset.UnionFindSet;

import java.util.*;

public class GraphByMatrix {
    public char[] arrayV;//顶点数组
    public int[][] matrix;//邻接矩阵
    public boolean isDirect;//是否为有向图

    //构造方法，提供size : 顶点个数
    //arrayV 顶点数组
    public GraphByMatrix(int size,boolean isDirect) {
        this.arrayV = new char[size];
        matrix = new int[size][size];
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(matrix[i],Integer.MAX_VALUE);
        }
        this.isDirect = isDirect;
    }

    //初始化顶点数组
    public void initArrayV(char[] arrayV) {
        for (int i = 0; i < arrayV.length; i++) {
            this.arrayV[i] = arrayV[i];
        }
    }

    //添加边
    public void addEdge(char srcV, char destV, int weight) {
        int indexSrc = getIndexV(srcV);
        int indexDest = getIndexV(destV);
        matrix[indexSrc][indexDest] = weight;
        //无向图是对称矩阵，单独处理
        if(!isDirect) {
            matrix[indexDest][indexSrc] = weight;
        }
    }

    //获得下标
    private int getIndexV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == v) {
                return i;
            }
        }
        return -1;
    }

    //获得顶点的度
    public int getDegreeOfV(char v) {
        int count = 0;
        int index = getIndexV(v);
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[index][i] != Integer.MAX_VALUE) {
                count++;
            }
        }

        //有向图，要单独处理入度
        if(isDirect) {
            for (int i = 0; i < matrix.length; i++) {
                if(i != index && matrix[i][index] != Integer.MAX_VALUE) {
                    count++;
                }
            }
        }

        return count;
    }

    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i] + " ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if(matrix[i][j] == Integer.MAX_VALUE) {
                    System.out.print("∞ ");
                } else {
                    System.out.print(matrix[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    public void bfs(char src) {
        int n = arrayV.length;
        boolean[] check = new boolean[n];//辅助数组
        Queue<Character> queue = new LinkedList<>();
        queue.offer(src);
        while(!queue.isEmpty()) {
            char ch = queue.poll();
            System.out.print(ch + " ");
            int index = getIndexV(ch);
            check[index] = true;
            for (int i = 0; i < n; i++) {
                if(matrix[index][i] != Integer.MAX_VALUE && !check[i]) {
                    queue.offer(arrayV[i]);
                    check[i] = true;
                }
            }
        }
        System.out.println();
    }

    public void dfs(char v) {
        boolean[] visited = new boolean[arrayV.length];
        int index = getIndexV(v);
        dfsChile(index,visited);
    }

    private void dfsChile(int index, boolean[] visited) {
        System.out.print(arrayV[index] + "->");
        visited[index] = true;

        for (int i = 0; i < arrayV.length; i++) {
            if(!visited[i] && matrix[index][i] != Integer.MAX_VALUE) {
                dfsChile(i,visited);
            }
        }
    }

    //创建边类
    static class Edge {
        public int src;
        public int dest;
        public int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public int Kruskal(GraphByMatrix minTree) {
        //创建优先级队列
        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        //将所有的边纳入到优先级队列中
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Integer.MAX_VALUE) {
                    queue.offer(new Edge(i,j,matrix[i][j]));
                }
            }
        }

        UnionFindSet unionFindSet = new UnionFindSet(n);

        //构建生成树
        int size = 0;
        int totalWeight = 0;
        while(!queue.isEmpty() && size < n - 1) {
            Edge tmp = queue.poll();
            int src = tmp.src;
            int dest = tmp.dest;
            if(!unionFindSet.isSameSet(src,dest)) {
                minTree.addEdge(arrayV[src],arrayV[dest], tmp.weight);
                unionFindSet.union(src,dest);
                totalWeight += tmp.weight;
                size++;
            }
        }

        if(size < n - 1) {
            return -1;
        }
        return totalWeight;
    }

    public int prime(GraphByMatrix minTree, char src) {
        int totalWeight = 0;
        int n = arrayV.length;
        int size = 0;

        //构建优先级队列
        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        UnionFindSet unionFindSet = new UnionFindSet(n);
        int index = getIndexV(src);
        for (int i = 0; i < n; i++) {
            if(matrix[index][i] != Integer.MAX_VALUE) {
                queue.offer(new Edge(index,i,matrix[index][i]));
            }
        }

        while(!queue.isEmpty()) {
            Edge tmp = queue.poll();
            int indexSrc = tmp.src;
            int indexDest = tmp.dest;
            int weight = tmp.weight;
            if(!unionFindSet.isSameSet(indexSrc,indexDest)) {
                unionFindSet.union(indexSrc,indexDest);
                minTree.addEdge(arrayV[indexSrc],arrayV[indexDest],weight);
                for (int i = 0; i < n; i++) {
                    if(matrix[indexDest][i] != Integer.MAX_VALUE) {
                        queue.offer(new Edge(index,i,matrix[index][i]));
                    }
                }
                totalWeight += weight;
                size++;
            }
        }

        if(size < n - 1) {
            return -1;
        }
        return totalWeight;
    }

    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndexV(vSrc);
        //距离数据初始化
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[srcIndex] = 0;
        //路径数组初始化
        Arrays.fill(pPath,-1);
        pPath[srcIndex] = 0;

        int n = arrayV.length;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(matrix[i][j] != Integer.MAX_VALUE &&
                            dist[i] + matrix[i][j] < dist[j]) {
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Integer.MAX_VALUE &&
                        dist[i] + matrix[i][j] < dist[j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public void dijkstra(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndexV(vSrc);
        //距离数据初始化
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[srcIndex] = 0;
        //路径数组初始化
        Arrays.fill(pPath,-1);
        pPath[srcIndex] = 0;
        //当前顶点是否被访问过？
        int n = arrayV.length;
        boolean[] s = new boolean[n];

        //n个顶点,要更新n次，每次都要从0下标开始，找到一个最小值
        for (int k = 0; k < n; k++) {
            int min = Integer.MAX_VALUE;
            int u = srcIndex;
            for (int i = 0; i < n; i++) {
                if(s[i] == false && dist[i] < min) {
                    min = dist[i];
                    u = i;//更新u下标
                }
            }
            s[u] = true;//u:s
            //松弛u连接出去的所有的顶点 v
            for (int v = 0; v < n; v++) {
                if(s[v] == false && matrix[u][v] != Integer.MAX_VALUE
                        && dist[u] + matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + matrix[u][v];
                    pPath[v] = u;//更新当前的路径
                }
            }
        }
    }

    public void floydWarShall(int[][] dist,int[][] pPath) {
        int n = arrayV.length;

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i],Integer.MAX_VALUE);
            Arrays.fill(pPath[i],-1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Integer.MAX_VALUE) {
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                }else {
                    pPath[i][j] = -1;
                }
                if(i == j) {
                    dist[i][j] = 0;
                    pPath[i][j] = -1;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE &&
                            dist[k][j] != Integer.MAX_VALUE &&
                            dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        //更新父节点下标
                        //pPath[i][j] = k;//不对
                        //如果经过了 i->k  k->j  此时是k
                        //i->x->s->k   k->..t->...x->j
                        pPath[i][j] = pPath[k][j];
                    }
                }
            }
        }
    }
}
